#include "solution.h"
#include "switch.h"

int begin=0;
int ending=0;

Solution::Solution(QWidget *parent)
    : QObject{parent}
{}

void Solution::get_route1(int be, int en, QVector<int>& path, QVector<QVector<int>>& allPaths) {
    visited[be] = 1; // 标记当前节点为已访问
    path.push_back(be); // 将当前节点加入路径中

    if (be == en) {
        // 当找到一条路径时，将当前 path 存入 allPaths
        allPaths.push_back(path);
    }
    else {
        Node* p = hnode[be]->next;
        while (p != NULL) {
            int a = p->val;
            if (visited[a] == 0)
                get_route1(a, en, path, allPaths); // 递归寻找路径
            p = p->next;
        }
    }

    visited[be] = 0; // 回溯，标记当前节点为未访问
    path.pop_back(); // 从路径中移除当前节点
}

void Solution::get_route(QVector<QVector<int>>& allPaths) {
    QVector<int> path;
    get_route1(begin, ending, path, allPaths);
}

void Solution::shortest_r(int be, int en, QVector<QVector<int>>& allPaths)
{
    QQueue<QVector<int>> qu;
    QList<int> list;
    list.append(be);
    qu.enqueue(list);  // 将起始节点be作为路径的起点
    visited[be] = 1; // 标记起始节点be为已访问

    while (!qu.empty()) {
        QVector<int> path = qu.front();
        qu.dequeue();

        int last_node = path.back(); // 获取当前路径的最后一个节点

        // 如果最后一个节点是目标节点en，将该路径添加到结果集allPaths中
        if (last_node == en) {
            allPaths.push_back(path);
        }

        // 遍历最后一个节点的邻居节点
        Node* p = hnode[last_node]->next;
        while (p != NULL) {
            int a = p->val;
            if (visited[a] == 0) {
                visited[a] = 1; // 标记节点w为已访问
                QVector<int> new_path = path; // 复制当前路径
                new_path.push_back(a); // 将节点w加入到路径中
                qu.enqueue(new_path); // 将新路径加入到队列中
            }
            p = p->next;
        }
    }
}

void Solution::shortest(QVector<QVector<int>>& allPaths)
{
    shortest_r(begin, ending, allPaths);
}

